import java.util.Stack;

public class Solution1 {
        public boolean isValid(String s) {


            Stack<Character> stack = new Stack<>();

            for(int i = 0; i< s.length();i++) {
                char ch = s.charAt(i);
                if(ch == '(' || ch == '[' || ch == '{') {
                    //如果是左括号，就入栈
                    stack.push(ch);
                }else{
                    if(stack.empty()) {
                        //遇到右括号了，但是当前栈是空的
                        return false;
                    }
                    char c = stack.peek();
                    if(c == '(' && ch == ')' || c == '[' && ch == ']' || c == '{' && ch == '}' ) {
                        stack.pop();//当前的这两个括号是匹配的
                    }else{
                        //当前这两个括号 不匹配
                        return false;
                    }
                }
            }

            if(!stack.empty()) {
                return false;//栈当中 还存在左括号！
            }

            return true;
        }

    }
